題目

• The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

• And then read line by line: "PAHNAPLSIIGYIR"

• Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

解法

首先觀察一下:

numRows = 3:
P   A   H   N
A P L S I I G
Y   I   R

• 可以看到逐列讀取:
  • P->A->H->N的index為 0->4->8->12，一次跳4。
  • A->P->L->S->I->I->G的index為1->3->5->7->9->11->13，一次跳2。
  • Y->I->R的index為 2->6->10，一次跳4。

numRows = 4:
P     I    N
A   L S  I G
Y A   H R
P     I

• 可以看到逐列讀取:

  • P->I->N的index為 0->6->12，一次跳6。
  • A->L->S->I->G的index為1->5->7->11->13，可以看到2個跳值，4與2輪流。
  • Y->A->H->R的index為 2->4->8->10，可以看到2個跳值，2與4輪流。
  • P->I的index為3->9，一次跳6。

• 我們能得到幾件事情:

  • 第一列與最後一列，只有一個跳值。
  • 中間列會有2個跳值 (numRows=3時沒有，但我們能把它想像成有2個，沒差)。
  • 最大跳值會是 numRows x 2 - 2 (numRows=3,最大跳4， numRows=4,最大跳6)

所以我們能用一個for loop，i為每列第一個index(依上面例子，開頭順序0,1,2,3)，並找出跳的規律，就解決問題了!。
至於2個跳值應該多少，大家就自己觀察一下啦!

Code

class Solution {
public:
    string convert(string s, int numRows) {
        
        int max_increase; //最大跳值
        int inc0, inc1; //2個跳值
        int flag; //讓跳值輪流用
        
        string ans = "";   
        
        max_increase = (numRows == 1) ? 1 : numRows * 2 - 2; 
       
        for(int i = 0; i < numRows; i++){
            
            int j = i; 
            
            inc0 = (i == numRows - 1) ? max_increase : max_increase - i * 2; //跳值1
            inc1 = (i == 0) ? max_increase : i * 2; //跳值2
            
            flag = 0;   
            
            while(j < s.length()){
                ans.push_back(s[j]); //儲存至ans
                
                j += (flag == 0)? inc0 : inc1; //輪流跳
                
                flag = flag^1;  //用xor翻轉旗標 (0->1, 1->0)
            }
            
        }
        return ans;
    }
};